package hot100;

public class Solution279 {
    public int numSquares(int n) {
        int near = getNearNum(n);
        if (near * near == n) {
            return 1;
        }
        int[] nums = new int[near];
        for (int i = 1; i <= near; i++) {
            nums[i - 1] = getSquares(n - i * i) + 1;
        }
        int min = Integer.MAX_VALUE;
        for (int i : nums) {
            min = Math.min(min, i);
        }
        return min;

    }

    public int getSquares(int n) {
        int near = getNearNum(n);
        if (near <= 1) {
            return n;
        }
        return getSquares(n - near * near) + 1;

    }

    public int getNearNum(int n) {
        if (n <= 1) {
            return n;
        }
        int num = n / 2;
        while (num * num > n) {
            num--;
        }
        return num;
    }

    public static void main(String[] args) {
        Solution279 solution279 = new Solution279();
        System.out.println(solution279.numSquares(12));
    }
}
